"""604"""
import re

"""
设计并实现一个迭代压缩字符串的数据结构。给定的压缩字符串的形式是，每个字母后面紧跟一个正整数，表示该字母在原始未压缩字符串中出现的次数。

设计一个数据结构，它支持如下两种操作： next 和 hasNext。

next() - 如果原始字符串中仍有未压缩字符，则返回下一个字符，否则返回空格。
hasNext() - 如果原始字符串中存在未压缩的的字母，则返回true，否则返回false。
"""
"""
示例 1：

输入：
    ["StringIterator", s.next(), s.next(), s.next(), s.next(), s.next(), s.next(), s.hasNext(), s.next(), s.hasNext()]
    [["L1e2t1C1o1d1e1"], [], [], [], [], [], [], [], [], []]
输出：
    [null, "L", "e", "e", "t", "C", "o", true, "d", true]

解释：
    StringIterator stringIterator = new StringIterator("L1e2t1C1o1d1e1");
    stringIterator.next(); // 返回 "L"
    stringIterator.next(); // 返回 "e"
    stringIterator.next(); // 返回 "e"
    stringIterator.next(); // 返回 "t"
    stringIterator.next(); // 返回 "C"
    stringIterator.next(); // 返回 "o"
    stringIterator.hasNext(); // 返回 True
    stringIterator.next(); // 返回 "d"
    stringIterator.hasNext(); // 返回 True
 

提示：
    1 <= compressedString.length <= 1000
    compressedString 由小写字母、大写字母和数字组成。
    在 compressedString 中，单个字符的重复次数在 [1,10 ^9] 范围内。
    next 和 hasNext 的操作数最多为 100 。
"""


class StringIterator:
    # 解压属于严重耗时操作，慎用
    def __init__(self, compressedString: str):
        self.compressedString = compressedString
        self.char = ""
        n = len(compressedString)
        i = 0
        while i < n:
            c = compressedString[i]
            x = 0
            i += 1
            while i < n and compressedString[i].isdigit():
                x = x * 10 + int(compressedString[i])
                i += 1
            self.char += c * x

    def next(self) -> str:
        if not self.char:
            return " "
        next_char = self.char[0]
        self.char = self.char[1:]
        return next_char

    def hasNext(self) -> bool:
        return len(self.char) != 0


class StringIterator_v2:
    def __init__(self, compressedString: str):
        self.char_freq = []
        n = len(compressedString)
        i = 0
        while i < n:
            c = compressedString[i]
            x = 0
            i += 1
            while i < n and compressedString[i].isdigit():
                x = x * 10 + int(compressedString[i])
                i += 1
            self.char_freq.append([c, x])

    def next(self) -> str:
        if not self.char_freq:
            return " "
        c, f = self.char_freq[0]
        if f == 1:
            self.char_freq.pop(0)
        else:
            self.char_freq[0][1] -= 1
        return c

    def hasNext(self) -> bool:
        return len(self.char_freq) != 0


class StringIterator_v3:  # 正则匹配 + 模拟
    def __init__(self, compressedString: str):
        self.compressedString = compressedString

    def next(self) -> str:
        prefix = re.findall(r'^[a-zA-Z][0-9]*', self.compressedString)
        if prefix:
            char = prefix[0][0]
            n = int(prefix[0][1:])
        else:
            return " "
        if n != 1:
            replace_str = char + str(n - 1)
            self.compressedString = re.sub(r'^[a-zA-Z][0-9]*', replace_str, self.compressedString)
            return char
        else:
            self.compressedString = re.sub(r'^[a-zA-Z][0-9]*', '', self.compressedString)
            return char

    def hasNext(self) -> bool:
        prefix = re.findall(r'^[a-zA-Z][0-9]*', self.compressedString)
        for c in prefix:
            if c.isalnum():
                return True
        return False


if __name__ == '__main__':
    s1 = "L1e2t1C1o1d1e1"
    s2 = "z82d333a213123123"
    s = StringIterator(s1)

    o1 = [s.next(), s.next(), s.next(), s.next(), s.next(), s.next(), s.hasNext(), s.next(), s.hasNext()]
    o2 = [
        s.next(), s.next(), s.next(), s.next(), s.next(), s.next(), s.hasNext(), s.next(), s.next(), s.next(),
        s.next(), s.next(), s.next(), s.hasNext(), s.next(), s.next(), s.hasNext(), s.next(), s.next(), s.next(),
        s.next(), s.next(), s.next(), s.hasNext(), s.next(), s.hasNext(), s.next(), s.next(), s.hasNext(), s.next(),
        s.hasNext(), s.next(), s.next(), s.next(), s.next(), s.next(), s.next()
    ]
    for i in o1:
        print(i)
